# Definition for a binary tree node.
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]
def buildTree(preorder, inorder) -> TreeNode:
    #先确定根节点
    if len(preorder)==1 and len(inorder)==1:
        print(preorder,inorder)
        return TreeNode(preorder[0])

    print(preorder,inorder)
    root=TreeNode(preorder[0])
    inorderIndex=inorder.index(preorder[0])
    root.left=buildTree(preorder[1:1+inorderIndex],inorder[:inorderIndex])
    root.right=buildTree(preorder[inorderIndex+1:],inorder[inorderIndex+1:])

    return root



root=buildTree(preorder,inorder)

def dfs(root):
    if root.left==None and root.right==None:
        print(root.val)
        return None

    if root.left:
        dfs(root.left)
    print(root.val)
    if root.right:
        dfs(root.right)
dfs(root)